package com.cty._05_Ability._55_02_BalancedBinaryTree;

/**
 * @Auther: cty
 * @Date: 2020/7/22 16:41
 * @Description: 面试题55（二）：平衡二叉树
 * 题目：输入一棵二叉树的根结点，判断该树是不是平衡二叉树。如果某二叉树中
 * 任意结点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。
 * @version: 1.0
 */
public class BalancedBinaryTree {
    /**
     * 方法一：重复遍历节点多次
     * 缺陷：存在重复遍历问题
     * @param treeRoot
     * @return
     */
    public static boolean isBalanced(BinaryTreeNode treeRoot){
        if(treeRoot == null)
            return true;

        int nLeft = treeDepth(treeRoot.leftChild);
        int nRight = treeDepth(treeRoot.rightChild);
        int diff = nLeft - nRight;
        if(diff>1 || diff<-1)
            return false;

        return isBalanced(treeRoot.leftChild) && isBalanced(treeRoot.rightChild);
    }  // end isBalanced()

    private static int treeDepth(BinaryTreeNode treeRoot){
        if(treeRoot == null)
            return 0;

        int nLeft = treeDepth(treeRoot.leftChild);
        int nRight = treeDepth(treeRoot.rightChild);

        return (nLeft>nRight)?(nLeft+1):(nRight+1);
    }  // end treeDepth()


    private static boolean isBalanced;
    /**
     * 方法二：后序遍历实现
     * 优点：只遍历一次，提高了效率
     * 确定：需要借助全局变量
     * @param treeRoot
     * @return
     */
    public static boolean isBalanced2(BinaryTreeNode treeRoot){
        if(treeRoot == null)
            return true;

        isBalanced = true;
        treeDepth2(treeRoot);
        return isBalanced;
    }  // end isBalanced2()

    private static int treeDepth2(BinaryTreeNode treeRoot){
        if(treeRoot == null)  // 此时的treeRoot不会是原始树根节点
            return 0;

        int nLeft = treeDepth2(treeRoot.leftChild);
        int nRight = treeDepth2(treeRoot.rightChild);

        int diff = nLeft - nRight;
        if(diff>1 || diff<-1)
            isBalanced = false;

        return (nLeft>nRight)?(nLeft+1):(nRight+1);
    }  // end treeDepth2()

}  // end class

class BinaryTreeNode {
    int value;
    BinaryTreeNode leftChild;
    BinaryTreeNode rightChild;

    public BinaryTreeNode(){}
    public BinaryTreeNode(int value){this.value = value;}
} // end class
